using System;
using System.Collections.Generic;
using System.Text;

namespace LannyPractiseCode.Shu
{
    //创建结点类
    //为了让HuffmanNode对象持续排序Collections集合排序
    //让Node实现IComparable接口
    public class HuffmanCode
    {

        //赫夫曼树生成对应的赫夫曼编码
        //思路：
        //1.将赫夫曼表存放在Map<Byte,String>形式,比如
        //32->01,  97->100  100->11000 等等 
        public static Dictionary<byte,string> huffmanCodes=new Dictionary<byte,string>();
        //2.在生成赫夫曼编码表示，需要取拼接路径，定义一个StringBuilder 存储某个叶子结点的路径。
        public static StringBuilder stringBuilder=new StringBuilder();

        /// <summary>
        /// 功能：将传入的node的所有叶子结点的赫夫曼编码，存放到到静态huffmanCodes集合中。。
        /// </summary>
        /// <param name="node">传入结点</param>
        /// <param name="code">路径：左子节点：0    右子节点：1</param>
        /// <param name="stringBuilder">用于拼接路径</param>
        public static void GetHuffmanCodes(HuffmanCodeNode node,String code,StringBuilder stringBuilder)
        {
            StringBuilder stringBuilder2=new StringBuilder();
            stringBuilder2.Append(stringBuilder);
            stringBuilder2.Append(code);

            if(node!=null)//如果node==null，不处理
            {
                //判断当前node是叶子还是非叶子节点
                if(node.data==0)//非叶子结点
                {
                    //递归处理，向左递归
                    GetHuffmanCodes(node.Left,"0",stringBuilder2);
                    GetHuffmanCodes(node.Right,"1",stringBuilder2);
                }
                else
                {
                     huffmanCodes.Add(node.data,stringBuilder2.ToString());
                }
            }
        }

        //获取结点的个数
        public static List<HuffmanCodeNode> GetNodes(byte[] bytes)
        {
            List<HuffmanCodeNode> nodes=new List<HuffmanCodeNode>();

            //遍历byte，统计每一个byte出现的次数-map
            //byte 就
            Dictionary<Byte,int> counts=new Dictionary<byte, int>();
            foreach (var item in bytes)
            {
                if(counts.ContainsKey(item))
                {
                    int count=counts[item];
                    counts[item]=count+1;
                }
                else
                {
                    counts.Add(item,1);
                }
            }

            //把每一个键值转换成Node对象，并加入到Nodes集合中
            foreach (var item in counts)
            {
                nodes.Add(new HuffmanCodeNode(item.Key,item.Value));
            }

            return nodes;
        }

        //创建哈夫曼树
        public static HuffmanCodeNode CreateHuffmanTree(List<HuffmanCodeNode> nodes)
        {
            while(nodes.Count>1)
            {
                //排序从小到大
                nodes.Sort();
                //取出第一课最小的二叉树
                HuffmanCodeNode leftNode=nodes[0];
                //取出第二课最小的二叉树
                HuffmanCodeNode rightNode=nodes[1];
                //创建一颗新的二叉树，它的根节点没有data，只有权值！！！！
                HuffmanCodeNode parent=new HuffmanCodeNode(0,leftNode.Weight+rightNode.Weight);
                parent.Left=leftNode;
                parent.Right=rightNode;

                //将已经处理的2颗二叉树从nodes移除
                nodes.Remove(leftNode);
                nodes.Remove(rightNode);

                //将新的二叉树加入到nodes
                nodes.Add(parent);
            }
            //最后这个节点 就是哈夫曼树的跟节点

            return nodes[0];
        }

        //前序遍历
        public static void PreOrder(HuffmanCodeNode root)
        {
            if(root!=null)
                root.PreOrder();
            else
                System.Console.WriteLine("赫夫曼殊为空！！");
        }
    
        ///<summary>
        /// 编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫量编码表，返回一个赫夫最编码压编后的byte[]
        /// </summary>
        /// <param name="bytes">bytes这时原始的字符串对应的byte[]</param>
        /// <param name="huffmanCodes">生成的赫夫曼编码map</param>
        /// <returns>返回赫夫曼编码处理后的byte[]</returns>
        /// 举例: String content = "i like like like java do you like a java"; =》byte[] contentBytes = content.getByte返回的是字符
        /// 串"101010001111111001000101111111000010111111100100101001111000100000110111010001111
        ///  =>对应的byte[ ] huffmanCodeBytes ,即8位对应一个byte , 放入到huffmanCodeBytes
        /// huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 -1 => 10100111(反码)=> 11011000=
        /// huffmanCodeBytes[1] = -88
        public static byte[] Zip(byte[] bytes,Dictionary<Byte,string> huffmanCodes)
        {
            //1.利用huffmanCodes将bytes 转成赫夫曼编码对应的字符串
            StringBuilder sb =new StringBuilder();

            foreach (var item in bytes)
                sb.Append(huffmanCodes[item]);

            //输出编码
            //System.Console.WriteLine(sb.ToString());
            //统计返回 bute[] 的长度
            int len=0;
            if(sb.Length %8==0)
                len=sb.Length /8;
            else
                len=sb.Length/8+1;

            //创建存储压缩后的byte数组
            int index=0;//记录第几个byte
            byte[] huffmanCodeBytes=new byte[len];
            for (int i = 0; i < sb.Length; i+=8)//因为是每8对应一个bute，所以步长+8
            {
                string strByte="";

                if(i+8>sb.Length)//不够8位
                    strByte=sb.ToString().Substring(i);
                else
                    strByte=sb.ToString().Substring(i,8);

                //将strByte转成一个byte,放入到huffmanCodeBytes
                System.Console.WriteLine(strByte);
                huffmanCodeBytes[index]=(byte)Convert.ToInt32(strByte,2);
                index++;
            }

            return huffmanCodeBytes;
        }
    }
}